A simple data packet switching system found in the prior art consists of a N×N switch fabric S (often a crossbar) connecting N input ports I0, I1, . . . IN−1 to N output ports O0, O1, . . . ON−1. In a common configuration, illustrated in FIG. 1, there are buffers IB0, IB1, . . . IBN−1 102 at the inputs that hold packets waiting to enter the crossbar switch 104. In some configurations, there may also be output buffers OB0, . . . OBN−1 106. Additionally, there is some logic (not pictured) to control the crossbar.
In one simple embodiment, with N input ports, there is a round robin method of controlling the switch. The round robin procedure first permutes the integers 0, 1, . . . N−1 into a sequence P(0), P(1), . . . P(N−1). Then, the logic that sets the N×N switch first examines the data packets at the input port buffer IBP(0) and selects a packet p0 that it most desires to send through the switch. If the target output port or target output port buffer is able to receive a packet, then the logic sets the switch connection to send p0 to its target. If the target output of p0 is not in a condition to receive p0, then the logic attempts to send another packet p1 in IBP(0) to its target. This process is continued until either: 1) A packet pn in IBP(0) is found that can be sent to its target; or 2) No such packet is found. In case 1, one crossbar connection is set. In case 2, no message from IBP(0) will be sent in the next message sending period. At this point, the logic sets the switch to send a packet in IBP(1) through the switch. For a packet q to be sent from IBP(1) to it's target, it is necessary that the target is in a condition ready to receive a message, and moreover, it is necessary that p and q are not sent to the same output. In general, this process is continued subject to the constraint that no packet in a buffer IBP(K) is sent to an output already scheduled to receive a packet from IBP(J), where J<K. Once the switch is completely set, then the packets are sent and the procedure is repeated with a new permutation Q(0), Q(1), . . . Q(N−1). The reason for the new permutation is that the early members of the sequence have an advantage over the later members and in order to be fair, it is necessary that the integers be rearranged for each setting of the switch.
There are a number of disadvantages to the message management scheme of the prior art: 1) the setting of the switch is time consuming; 2) the setting of the switch is not optimal; 3) no two output ports can simultaneously receive distinct messages from the same input port. One example where the setting is not optimal is in the case where a low priority message in IBP(J) blocks a high priority message in IBP(K), where J<K. While there are numerous variations to shared memory switching systems, the same three problems persist with each of the variations. An example of a system that overcomes disadvantages 1 and 3 is described in “A Multiple Level Minimum Logic Network” (MLML network) is described in U.S. Pat. No. 5,996,020, granted to Coke S. Reed on Nov. 30, 1999, (“Invention #1”), the teachings of which are incorporated herein by reference. Another example of a system overcoming disadvantages 1 and 3 is described in U.S. patent application Ser. No. 09/009,703 filed by John Hesse on Jan. 20, 1998. (“Invention #2” entitled: “A Scaleable Low Latency Switch for Usage in an Interconnect Structure”). Disadvantage 2 is overcome in the system described in U.S. patent application Ser. No. 09/919,467 entitled, “Means and Apparatus for a Scaleable Congestion Free Switching System with Intelligent Control” (Invention #8). This system uses interconnect structures of the type described in Inventions #1 and #2. A key idea in Invention #8 is to control packet entry into the data switch by jointly considering all of the messages targeted for a common output port.
It is the purpose of the present invention to use novel new techniques to overcome disadvantages 1, 2, and 3. These techniques use a key idea of Invention #8, of establishing control of the system based on comparing messages targeted for a common output port. However, the present invention does not require the use of self routing networks but rather relies on a novel new data management technique. The present invention shows how to manage shared memory switching systems effectively.